//
// Created by lxinp on 2022/8/10.
//

#include <iostream>
#include <sstream>
#include "binary_tree.h"
#include "../utils/random.h"
#include "../utils/print_tree.h"


//template class BinaryTreeNodeDescriptor<Node>;
/**
 * This template class is taken from:
 * https://www.students.cs.ubc.ca/~cs-221/2019W2/labs/trees/
 * @tparam Node
 */
//template<typename Node>
//class BinaryTreeNodeDescriptor
//        : public GenericNodeDescriptor<BinaryTreeNodeDescriptor<Node>> {
//public:
//    BinaryTreeNodeDescriptor(const Node* node_ptr) : node(node_ptr) {}
//    bool is_null() { return !node; }
//    std::string key() const {
//        std::stringstream ss;
//        ss << node->data;
//        return ss.str();
//    }
//    BinaryTreeNodeDescriptor left() const {
//        return BinaryTreeNodeDescriptor(node->left);
//    }
//    BinaryTreeNodeDescriptor right() const {
//        return BinaryTreeNodeDescriptor(node->right);
//    }
//private:
//    const Node* node;
//};


template<typename T>
BinaryTree<T>::BinaryTree() : root(nullptr) {}


template<typename T>
BinaryTree<T>::BinaryTree(const BinaryTree<T>& other) : root(copy(other.root)) {}


template<typename T>
BinaryTree<T>::~BinaryTree() {
    clear(root);
}


template<typename T>
BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree<T>& other) {
    if (this != &other) {
        if (root) clear(root);
        root = copy(other.root);
    }
    return *this;
}


template<typename T>
void BinaryTree<T>::clear() {
    clear(root);
    root = nullptr;
}


template<typename T>
void BinaryTree<T>::insert(const T& data, bool sorted) {
    insert(root, data, sorted);
}


template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::copy(const Node* other) {
    if (!other) return nullptr;

    Node* curr_node = new Node(other->data);
    curr_node->left = copy(other->left);
    curr_node->right = copy(other->right);

    return curr_node;
}


template<typename T>
void BinaryTree<T>::clear(Node* subtree) {
    if (!subtree) return;

    clear(subtree->left);
    clear(subtree->right);
    delete subtree;
    subtree = nullptr;  // TODO: check if necessary
}


template<typename T>
void BinaryTree<T>::insert(Node* subtree, const T& data, bool sorted) {
    if (!subtree) {
        subtree = new Node(data);
        return;
    }
    if (sorted) {
        if (data < subtree->data) insert(subtree->left, data, sorted);
        else insert(subtree->right, data, sorted);
    } else {
        if (util::urand() % 2 == 0) insert(subtree->left, data, sorted);
        else insert(subtree->right, data, sorted);
    }
}


template<typename T>
int BinaryTree<T>::height() const {
    return height(root);
}


template<typename T>
void BinaryTree<T>::print() const {
//    print_tree(BinaryTreeNodeDescriptor<Node>(root));
}


template<typename T>
void BinaryTree<T>::mirror() {
    mirror(root);
}


template<typename T>
bool BinaryTree<T>::is_ordered() const {
    return is_ordered(root, nullptr, nullptr);
}


template<typename T>
void BinaryTree<T>::mirror(Node* subtree) {
    if (!subtree) return;

    Node* temp = subtree->left;
    subtree->left = subtree->right;
    subtree->right = temp;

    mirror(subtree->left);
    mirror(subtree->right);
}


template<typename T>
bool BinaryTree<T>::is_ordered(const Node* subtree, const Node* left, const Node* right) const {
    if (!subtree) return true;
    if (left && subtree->data <= left->data) return false;
    if (right && subtree->data >= right->data) return false;
    if (!is_ordered(subtree->left, left, subtree)) return false;
    if (!is_ordered(subtree->right, subtree, right)) return false;
    return true;
}


template<typename T>
int BinaryTree<T>::height(const Node* subtree) const {
    if (!subtree) return 0;
    return 1 + std::max(height(subtree->left), height(subtree->right));
}

template class BinaryTree<int>;
